This invention relates generally to computer networks and, more particularly, to routing updates associated with routing protocols used in a computer network.
A computer network is a geographically distributed collection of interconnected communication links for transporting data between nodes, such as computers. Many types of computer networks are available, with the types ranging from Local Area Networks (LANs) to Wide Area Networks (WANs). The nodes typically communicate by exchanging discrete frames or packets of data according to pre-defined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate node, called a router, to extend the effective xe2x80x9csizexe2x80x9d of each network. Since management of a large system of interconnected computer networks can prove burdensome, smaller groups of computer networks may be maintained as autonomous systems or routing domains. The networks within a routing domain are typically coupled together by conventional xe2x80x9cintradomainxe2x80x9d routers. Yet it still may be desirable to increase the number of nodes capable of exchanging data; in this case, xe2x80x9cinterdomainxe2x80x9d routers executing interdomain routing protocols are used to interconnect nodes of the various routing domains. An example of an interdomain routing protocol is the Border Gateway Protocol (BGP) which performs routing between autonomous systems by exchanging routing and reachability information among interdomain routers of the systems. The interdomain routers configured to execute the BGP protocol, called BGP routers, maintain routing tables, transmit routing update messages and render routing decisions based on routing metrics.
Each BGP router maintains a routing table (related to BGP) that lists all feasible paths to a particular network. BGP peer routers residing in the autonomous systems exchange routing information under certain circumstances. Incremental updates to the routing table are generally performed. For example, when a BGP router initially connects to the network, the peer routers may exchange the entire contents of their routing tables. Thereafter when changes occur to those contents, the routers exchange only those portions of their routing tables that change in order to update their peers"" tables. These update messages, which are sent in response to routing table changes, represent incremental updates that advertise only an optimal path to a particular network or that withdraw its reachability to the network. The BGP routing protocol is well-known and described in detail in Request For Comments (RFC) 1771, by Y. Rekhter and T. Li (1995), and Interconnections, Bridges and Routers, by R. Perlman, published by Addison Wesley Publishing Company, at pages 323-329 (1992), all disclosures of which are hereby incorporated by reference.
Broadly stated, a BGP router generates routing update messages for an adjacency or neighbor peer router by xe2x80x9cwalking-throughxe2x80x9d the routing table, identifying changes and applying appropriate routing policies. A routing policy is information that enables a BGP router to rank routes according to filtering and preference (i.e., the xe2x80x9coptimal routexe2x80x9d). Routing updates provided by the update message allows BGP routers of the autonomous systems to construct a consistent view of the network topology. The update messages are typically sent using a reliable transport, such as the Transmission Control Protocol (TCP), to ensure reliable delivery. TCP is a transport protocol implemented by a transport layer of the Internet Protocol (IP) architecture; the term TCP/IP is commonly used to denote this architecture. The TCP/IP architecture is well-known and described in Computer Networks, 3rd Edition, by Andrew S. Tanenbaum, published by Prentice-Hall (1996).
Generation of a routing update message by a router in accordance with a conventional update process may involve the following steps: (1) identifying a route in the routing table that has changed; (2) applying a per-neighbor route filtering policy, if appropriate; and (3) formating an update message, if appropriate. There is typically one or more paths associated with each route entry of the routing table; update message generation is concerned with the best path from among these paths. An entry version number is typically maintained for each route entry and used for incremental update operations. A routing table version number is also maintained and used to indicate a xe2x80x9clevelxe2x80x9d of the routing table. The table version number is incremented each time there is a change to the routing table. Moreover each time there is a change to an entry in the routing table, such as when the entry is added or deleted or when there is a best path change, the table version number is incremented and the entry version number is set to that incremented value.
In addition, a neighbor version number may be maintained in a neighbor data structure for each neighbor to indicate whether the neighbor is up-to-date with all route changes in the routing table. For example, the neighbor version number may be compared with the entry version numbers and a route may be eligible for further consideration of routing updates to the neighbor if its entry version number is greater than the neighbor version number. The neighbor version number is set to the table version number after all entries in the route table have been evaluated (and advertised if necessary) for the neighbor.
In certain situations, however, routing updates are not necessary for a neighbor having a neighbor version number that is less than an entry version number. FIG. 1 is a schematic block diagram of a conventional computer network 100 comprising a plurality of autonomous systems AS1-3 configured to exchange routing information with (i.e., maintain) a plurality of xe2x80x9cexternalxe2x80x9d neighboring peer routers residing in the autonomous systems. Specifically, AS1-2 maintains external peers B2-B3 and B2xe2x80x2-B3xe2x80x2, while AS2-3 maintains external peers B4-B5.
Assume that AS1 advertises different multi-exit discriminator (MED) values MED1, MED2 to AS2 over B2-B3 and B2xe2x80x2-B3xe2x80x2, respectively, for a particular route X. A MED value is an optional non-transitive attribute of an update message. The MED value is used by an updating BGP xe2x80x9csenderxe2x80x9d in, e.g., AS1, to discriminate among multiple exit points to a BGP xe2x80x9creceiverxe2x80x9d in a neighboring autonomous system, such as AS2. Further assume a path (i.e., the greater MED value) is initially advertised as a best path for route X by AS1 to AS2, and AS2 advertises that path to AS3. A preferred path (i.e., the lesser MED value) is subsequently advertised as the best path for X by AS1 to AS2. AS2 transitions the best path to this preferred path and increments the entry version number for route X. As a result, an update message for route X may be sent to AS3. This update message is considered a duplicate by AS3 because (from its point of view) there is no change for route X. Since the generation and transmission of routing update messages by the sender as well as the processing of these messages by the receiver consume resources, it would be advantageous to provide a technique that avoids generation of such unnecessary routing updates.
The invention comprises a technique that allows selective generation of routing update messages by a router for its neighboring peer routers of a computer network. Broadly stated, when an entry version number of a route is incremented, the reason (i.e., xe2x80x9cwhat has changedxe2x80x9d) for the change in the best path of the route is identified and recorded. That is, each time there is a new version of a route, attributes of the best path for the new version and the previous version of the route are compared and the changes are recorded. According to the selective routing update technique, recordation of the reason is effected using change flags. These flags, along with the characteristics of each neighbor, are processed by the router when determining whether the route is eligible for further consideration of routing updates to the neighbor.
In the illustrative embodiment, each change flag comprises a bit flag used to record, e.g., each of the following changes: (i) transitive attribute change; (ii) next-hop change; (iii) community change; (iv) interior gateway protocol (IGP) metric (to the next-hop) change; and (v) change in the best path. The bit flags are cumulative and cleared after the current version of a route has been evaluated (and sent if appropriate) for all neighbors. For example, if the entry version number of a route entry is incremented solely because of an IGP metric change and the receiving neighbor does not require notice of such a change, then generation of routing update message for the neighbor can be obviated.
Advantageously, the inventive technique minimizes generation of unnecessary (i.e., duplicate) routing update messages and improves network stability and scalability. In addition, the selective routing update technique provides a foundation for extending functionality in the area of routing updates.